/**
 * describe:
 *
 * @author chaP
 * @date 2019/03/23
 */
package CodingTest.AC20190323;

/**
 *题目描述
 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

 思路：
 设圆环的长度：n
 圆环外长度：w
 快慢指针：p1：每次走一步
          p2：每次走两步
 两环在圆环里相遇时所走的长度：y
 故p1和p2在圆环里相遇：w+kn+y = 2(w+y) 故w=kn-y,则设置p2为头节点，走过w时就与p1在入口处相遇
 */
public class EntryNodeOfLoop {
    class ListNode{
        int val;
        ListNode next = null;
        ListNode(int val){
            this.val = val;
        }
    }
    public ListNode EntryNodeOfLoop(ListNode pHead){
        if(pHead ==null||pHead.next == null)return null;
        ListNode p1 = pHead; //慢指针
        ListNode p2 = pHead; //快指针
        while(p2 != null &&p1 != null){
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1==p2){
                p2 = pHead;
                while(p1 != p2){
                    p1 = p1.next;
                    p2 = p2.next;
                    if(p1 == p2 )
                        return p1;
                }
            }
        }
        return null;
    }
}
